深度優先搜尋 (DFS)

解題思路

1. 初始化：首先，我們使用深度優先搜尋（DFS）來遍歷 s 中的每一個節點。
2. 子樹比較：對於 s 中的每一個節點，我們需要判斷該節點的子樹是否與 t 相等。這需要我們再次使用深度優先搜索。
3. 同步遍歷：在比較子樹的過程中，我們讓兩個指標分別指向 s 的當前節點和 t 的根節點。然後，我們「同步移動」這兩個指標，也就是說，每次我們都同時遍歷這兩棵樹的下一個節點。
4. 節點比較：在「同步遍歷」的過程中，我們需要判斷兩棵樹在相同位置的節點是否相等。如果所有對應位置的節點都相等，那麼我們就可以說 s 的當前子樹與 t 相等。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！
我們將幫助您撰寫一份出色的履歷表，讓您在眾多求職者中脫穎而出。我們將為您提供專業的建議和指導，幫助您在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入 Line 讀書會，和大家一起實現夢想！

履歷諮詢	加入讀書會 (邀請碼：3858)

程式

class Solution {
    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        if (root == null && subRoot == null) return true
        else if (root == null) return false
        else if (subRoot == null) return false
        else {
            val candidate = find(root, subRoot)
            val result = areTreesSame(candidate, subRoot)
            if (result) return true
            else {
                val leftResult = isSubtree(root.left, subRoot)
                if (leftResult) return true
                return isSubtree(root.right, subRoot)
            }
        }
    }

    private fun find(t1: TreeNode?, t2: TreeNode?): TreeNode? {
        if (t1?.`val` == t2?.`val`) return t1
        val left = t1?.left?.let { find(it, t2) }
        if (left != null) return left
        return t1?.right?.let { find(it, t2) }
    }

    private fun areTreesSame(r1: TreeNode?, r2: TreeNode?): Boolean {
        return if (r1 == null && r2 == null) true
        else if (r1 == null) false
        else if (r2 == null) false
        else {
            if (r1.`val` != r2.`val`) false
            else areTreesSame(r1.left, r2.left) &&
                    areTreesSame(r1.right, r2.right)
        }
    }
}

複雜度分析

• 時間複雜度:

1. 深度優先搜尋：對於 中的每一個節點，我們都需要進行一次深度優先搜尋來與 進行比較。
2. 比較時間：每次比較的時間成本是 ，因為我們需要遍歷 中的每一個節點。
3. 總時間：因此，總的時間成本是 ，因為我們對 中的每一個節點都進行了一次比較。
   所以，漸進時間複雜度為 。

• 空間複雜度:
  堆疊空間使用：在任何時刻，堆疊空間的最大使用成本是 ，其中 是 的深度， 是 的深度。
  所以，漸進空間複雜度為 。

　更多演算法題解，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！

履歷諮詢	加入讀書會 (邀請碼：3858)